#include<string.h>
#include<string>
#include<sstream>
#include<queue>
#include<stack>
#include<math.h>
#include<unordered_map>
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<vector>

#define INT_MAX 0x7fffffff
#define MAXSIZE 0x7fffffff
using namespace std;


#define MAXSIZE 1000
#define INTMAX 2147483647
#define INTMIN -2147483648
//顺序栈
typedef struct SqStack
{
    int top;
    char data[MAXSIZE];
} SqStack;

//顺序表结构体
typedef struct SqList
{
    int data[MAXSIZE];
    int length;
} SqList;

//单链表结构体
typedef struct LNode
{
    int data;
    struct LNode *next;
} LNode;

typedef struct DLNode
{
    int data;
    struct DLNode *prior;
    struct DLNode *next;
} BLNode;

typedef struct DLNodeF
{
    int data;
    int freq = 0;
    struct DLNodeF *prior;
    struct DLNodeF *next;
} DLNodeF;

//二叉链表
typedef struct BTNode
{
    char data;//存放数据
    BTNode *lChild, *rChild;
}BTNode;

//线索二叉树： 相较于二叉树，线索二叉数多了ltag和rtag,用于标记该结点的左孩子和右孩子是否为空，是则为1，否为0，
typedef struct TBTNode
{
    char data;
    TBTNode *lChild, *rChild;
    int ltag,rtag;
}TBTNode;

//哈夫曼树HTNode 结点的带权路径长度，从树的根到该结点的路径长度 * 该结点的权值
//树的带权路径长度：树种所有叶结点的带权路径长度之和
typedef struct HTNode
{
    int weight;//结点的权，某种含义的数量（如重要性）
    TBTNode *parent,*lChild, *rChild;
}HTNode;